#ifndef MULTIINDEX_HPP
#define MULTIINDEX_HPP

#include <list>
#include <map>
#include <functional>
#include <type_traits>

namespace MultiIndex
{

//MultiIndexedContainer - multi indexed container, see unit tests for usage

template<typename T>
class MultiIndexedContainer
{
protected:
	typedef std::list<T> List;
	typedef typename List::const_iterator ListConstIt;

	enum
	{
		IndexId = -1
	};

public:
	typedef T value_type;
	typedef const T* const_pointer;
	typedef const T& const_reference;
	typedef size_t size_type;

	typedef ListConstIt const_iterator;

	template<int> class nth_iterator
	{
		// invalid index id
	};

	template<typename> class tagged_iterator
	{
		// invalid index id
	};

	template<int> class nth_key
	{
		// invalid index id
	};

	template<typename> class tagged_key
	{
		// invalid index id
	};

	// begin
	const_iterator begin() const
	{
		return const_iterator(m_data.begin());
	}

	// end
	const_iterator end() const
	{
		return const_iterator(m_data.end());
	}

	bool insert(const T& val)
	{
		m_data.push_front(val);
		return true;
	}

	size_type size() const
	{
		return m_data.size();
	}

	bool empty() const
	{
		return m_data.empty();
	}

	void erase(const const_iterator& pos)
	{
		m_data.erase(pos);
	}

	void clear()
	{
		m_data.clear();
	}

protected:
	void internal_erase(const const_iterator& pos)
	{
		erase(pos);
	}

	List m_data;
};


//key extractors

template<typename ValueType,
		typename IndexedFieldType,
		IndexedFieldType (ValueType::*field)>
class FieldKeyExtractor
{
public:
	typedef IndexedFieldType KeyType;
	
	const KeyType& operator()(const ValueType& val) const
	{
		return val.*field;
	}

	const KeyType& operator()(const ValueType* val) const
	{
		return val->*field;
	}
};

template<typename ValueType>
class IdentityKeyExtractor
{
public:
	typedef ValueType KeyType;

	const KeyType& operator()(const ValueType& val) const
	{
		return val;
	}

	const KeyType& operator()(const ValueType* val) const
	{
		return *val;
	}
};

//for foreign keys

template<typename KeyExtractor1, typename KeyExtractor2>
struct KeyFromKeyExtractor
{
public:
	typedef typename KeyExtractor1::KeyType KeyType;

	template<typename Arg>
	const KeyType& operator()(const Arg& arg)const
	{
		return KeyExtractor1()(KeyExtractor2()(arg));
	}

};

// indexes

template<typename BaseIndexerClass,
	typename KeyExtractor,
	typename IndexTag = std::tr1::remove_cv<std::tr1::remove_pointer<typename KeyExtractor::KeyType>::type>::type,
	typename Comparator = std::less<typename KeyExtractor::KeyType> >
class UniqueIndex : public BaseIndexerClass
{
public:
	typedef typename BaseIndexerClass::value_type value_type;
	typedef typename BaseIndexerClass::const_pointer const_pointer;
	typedef typename BaseIndexerClass::const_reference const_reference;

protected:	
	typedef typename BaseIndexerClass::List ListType;
	typedef typename ListType::const_iterator ListConstIterator;
	typedef typename KeyExtractor::KeyType IndexedFieldType;

	typedef std::map<const std::tr1::reference_wrapper<const IndexedFieldType>, ListConstIterator, Comparator> Map;
	typedef typename Map::const_iterator MapConstIterator;

protected:
	enum
	{
		IndexId = BaseIndexerClass::IndexId + 1,
	};

public:
	
	class const_iterator: public MapConstIterator
	{
	public:
		enum
		{
			IteratorId = IndexId
		};

		const_iterator()
			: MapConstIterator()
		{
		}

		const_iterator(const MapConstIterator& it)
			: MapConstIterator(it)
		{

		}

		const_pointer operator->() const
		{
			return &(**this);
		}

		const_reference operator*() const
		{
			return *getContainerIterator();
		}

		const_iterator& operator++()
		{	// preincrement
			++*((MapConstIterator*)this);
			return *this;
		}

		const_iterator operator++(int)
		{	// postincrement
			const_iterator tmp = *this;
			++*this;
			return tmp;
		}

		const_iterator& operator--()
		{	// predecrement
			--*((MapConstIterator*)this);
			return *this;
		}

		const_iterator operator--(int)
		{	// postdecrement
			const_iterator tmp = *this;
			--*this;
			return tmp;
		}

		ListConstIterator getContainerIterator() const
		{
			return (*((MapConstIterator*)this))->second;
		}
	};

	// iterator by index type helper
	template<int N>
	class nth_iterator : public BaseIndexerClass::nth_iterator<N>
	{

	};

	template<>
	class nth_iterator<IndexId>
	{
	public:
		typedef const_iterator type;
	};

	// iterator by tag type helper
	template<typename Tag>
	class tagged_iterator : public BaseIndexerClass::tagged_iterator<Tag>
	{

	};

	template<>
	class tagged_iterator<IndexTag>
	{
	public:
		typedef const_iterator type;
		enum
		{
			iteratorIndexId = IndexId
		};
	};

	// key type by index helper
	template<int N>
	class nth_key : public BaseIndexerClass::nth_key<N>
	{

	};

	template<>
	class nth_key<IndexId>
	{
	public:
		typedef IndexedFieldType type;
	};

	// key type by tag helper
	template<typename Tag>
	class tagged_key: public BaseIndexerClass::tagged_key<Tag>
	{

	};

	template<>
	class tagged_key<IndexTag>
	{
	public:
		typedef IndexedFieldType type;
		enum
		{
			keyIndexId = IndexId
		};
	};

	//constructors

	UniqueIndex()
	{
	}

	UniqueIndex(const UniqueIndex& other)
		: BaseIndexerClass(other)
	{
		buildIndex();
	}

	UniqueIndex& operator=(const UniqueIndex& other)
	{
		BaseIndexerClass::operator=(other);

		buildIndex();
	}

	//begin

	// begin by tag
	template<typename Tag> 
	typename tagged_iterator<Tag>::type begin() const
	{
		return tagged_begin<Tag>();
	}

	// begin by index
	template<int N> 
	typename nth_iterator<N>::type begin() const
	{
		return indexed_begin<N>();
	}


	// end
	// end by tag
	template<typename Tag> 
	typename tagged_iterator<Tag>::type end() const
	{
		return tagged_end<Tag>();
	}

	// end by index
	template<int N> 
	typename nth_iterator<N>::type end() const
	{
		return indexed_end<N>();
	}
	
	//insert
	bool insert(const value_type& val)
	{
		const Map::const_iterator& it = m_index.find(std::tr1::cref(KeyExtractor()(val)));

		if (it == m_index.end())
		{
			if (BaseIndexerClass::insert(val))
			{

				const ListConstIterator& dataBegin = m_data.begin();
				const value_type& frontRef = *dataBegin;
				m_index.insert(make_pair(std::tr1::cref(KeyExtractor()(frontRef)), dataBegin));

				return true;
			}
		}

		return false;
	}
	
	//erase
	template<typename Iterator>
	void erase(const Iterator& pos)
	{
		// copy iterator to list
		const ListConstIterator listIterator = pos.getContainerIterator();

		internal_erase(listIterator);
	}

	template<typename Iterator>
	void erase(const Iterator& from, const Iterator& to)
	{
		Iterator iter = from;
		while (iter != to)
		{
			erase(iter++);
		}
	}

	//tagged erase
	template<typename Tag>
	void erase(const typename tagged_key<Tag>::type& key)
	{
		erase<tagged_key<Tag>::keyIndexId>(key);
	}

	// index erase
	template<int N>
	void erase(const typename nth_key<N>::type& key)
	{
		const std::pair<typename nth_iterator<N>::type, typename nth_iterator<N>::type>& range = equal_range<N>(key);
		
		const typename nth_iterator<N>::type& end = range.second;
		typename nth_iterator<N>::type iter = range.first;

		while(iter != end)
		{
			erase(iter++);
		}
	}

	// count
	template<int N> 
	size_t count(const typename nth_key<N>::type& key) const
	{
		return indexed_count<N>(key);
	}

	template<typename Tag>
	size_t count(const typename tagged_key<Tag>::type& key) const
	{
		return tagged_count<Tag>(key);
	}

	// find
	template<int N> 
	typename nth_iterator<N>::type find(const typename nth_key<N>::type& key) const
	{
		return indexed_find<N>(key);
	}

	template<typename Tag>
	typename tagged_iterator<Tag>::type find(const typename tagged_key<Tag>::type& key) const
	{
		return tagged_find<Tag>(key);
	}

	// equal_range
	template<int N>
	std::pair<typename nth_iterator<N>::type, typename nth_iterator<N>::type> equal_range(const typename nth_key<N>::type& key) const
	{
		return indexed_equal_range<N>(key);
	}

	template<typename Tag>
	std::pair<typename tagged_iterator<Tag>::type, typename tagged_iterator<Tag>::type> equal_range(const typename tagged_key<Tag>::type& key) const
	{
		return tagged_equal_range<Tag>(key);
	}

	// upper bound
	template<int N>
	typename nth_iterator<N>::type upper_bound(const typename nth_key<N>::type& key) const
	{
		return indexed_upper_bound<N>(key);
	}

	template<typename Tag>
	typename tagged_iterator<Tag>::type upper_bound(const typename tagged_key<Tag>::type& key) const
	{
		return tagged_upper_bound<Tag>(key);
	}

	void clear()
	{
		m_index.clear();
		BaseIndexerClass::clear();
	}

protected:
	void internal_erase(const ListConstIterator& pos)
	{
		m_index.erase(std::tr1::cref(KeyExtractor()(*pos)));
		BaseIndexerClass::internal_erase(pos);
	}

	//internal begin
	template<int N> 
	typename nth_iterator<N>::type indexed_begin() const
	{
		return BaseIndexerClass::indexed_begin<N>();
	}

	template<>
	const_iterator indexed_begin<IndexId>() const
	{
		return const_iterator(m_index.begin());
	}

	template<typename Tag> 
	typename tagged_iterator<Tag>::type tagged_begin() const
	{
		return BaseIndexerClass::tagged_begin<Tag>();
	}

	template<>
	const_iterator tagged_begin<IndexTag>() const
	{
		return const_iterator(m_index.begin());
	}

	//internal end
	template<int N> 
	typename nth_iterator<N>::type indexed_end() const
	{
		return BaseIndexerClass::indexed_end<N>();
	}

	template<>
	const_iterator indexed_end<IndexId>() const
	{
		return const_iterator(m_index.end());
	}

	template<typename Tag> 
	typename tagged_iterator<Tag>::type tagged_end() const
	{
		return BaseIndexerClass::tagged_end<Tag>();
	}

	template<>
	const_iterator tagged_end<IndexTag>() const
	{
		return const_iterator(m_index.end());
	}

	//internal count
	template<int N> 
	size_t indexed_count(const typename nth_key<N>::type& key) const
	{
		return BaseIndexerClass::indexed_count<N>(key);
	}

	template<>
	size_t indexed_count<IndexId>(const IndexedFieldType& key) const
	{
		return m_index.count(std::tr1::cref(key));
	}

	template<typename Tag> 
	size_t tagged_count(const typename tagged_key<Tag>::type& key) const
	{
		return BaseIndexerClass::tagged_count<Tag>(key);
	}

	template<>
	size_t tagged_count<IndexTag>(const IndexedFieldType& key) const
	{
		return m_index.count(std::tr1::cref(key));
	}

	//internal find
	template<int N> 
	typename nth_iterator<N>::type indexed_find(const typename nth_key<N>::type& key) const
	{
		return BaseIndexerClass::indexed_find<N>(key);
	}

	template<>
	const_iterator indexed_find<IndexId>(const IndexedFieldType& key) const
	{
		return m_index.find(std::tr1::cref(key));
	}

	template<typename Tag> 
	typename tagged_iterator<Tag>::type tagged_find(const typename tagged_key<Tag>::type& key) const
	{
		return BaseIndexerClass::tagged_find<Tag>(key);
	}

	template<>
	const_iterator tagged_find<IndexTag>(const IndexedFieldType& key) const
	{
		return m_index.find(std::tr1::cref(key));
	}

	// internal equal range
	template<int N>
	std::pair<typename nth_iterator<N>::type, typename nth_iterator<N>::type> indexed_equal_range(const typename nth_key<N>::type& key) const
	{
		return BaseIndexerClass::indexed_equal_range<N>(key);
	}

	template<>
	std::pair<const_iterator, const_iterator> indexed_equal_range<IndexId>(const IndexedFieldType& key) const
	{
		return m_index.equal_range(std::tr1::cref(key));
	}

	template<typename Tag>
	std::pair<typename tagged_iterator<Tag>::type, typename tagged_iterator<Tag>::type> tagged_equal_range(const typename tagged_key<Tag>::type& key) const
	{
		return BaseIndexerClass::tagged_equal_range<Tag>(key);
	}

	template<>
	std::pair<const_iterator, const_iterator> tagged_equal_range<IndexTag>(const IndexedFieldType& key) const
	{
		return m_index.equal_range(std::tr1::cref(key));
	}
	
	// internal upper bound
	template<int N>
	typename nth_iterator<N>::type indexed_upper_bound(const typename nth_key<N>::type& key) const
	{
		return BaseIndexerClass::indexed_upper_bound<N>(key);
	}

	template<>
	const_iterator indexed_upper_bound<IndexId>(const IndexedFieldType& key) const
	{
		return m_index.upper_bound(std::tr1::cref(key));
	}

 	template<typename Tag>
	typename tagged_iterator<Tag>::type tagged_upper_bound(const typename tagged_key<Tag>::type& key) const
	{
		return BaseIndexerClass::tagged_upper_bound<Tag>(key);
	}

	template<>
	const_iterator tagged_upper_bound<IndexTag>(const IndexedFieldType& key) const
	{
		return m_index.upper_bound(std::tr1::cref(key));
	}

private:
	void buildIndex()
	{
		ListConstIterator it = m_data.begin();
		const ListConstIterator& endIt = m_data.end();

		while(it != endIt)
		{
			const value_type& valRef = *it;
			m_index.insert(make_pair(std::tr1::cref(KeyExtractor()(valRef)), it));
			++it;
		}
	}

	Map m_index;
};

template<typename BaseIndexerClass,
		typename KeyExtractor,
		typename IndexTag = std::tr1::remove_cv<std::tr1::remove_pointer<typename KeyExtractor::KeyType>::type>::type,
		typename Comparator = std::less<typename KeyExtractor::KeyType> >
class NonUniqueIndex : public BaseIndexerClass
{
public:
	typedef typename BaseIndexerClass::value_type value_type;
	typedef typename BaseIndexerClass::const_pointer const_pointer;
	typedef typename BaseIndexerClass::const_reference const_reference;

protected:	
	typedef typename BaseIndexerClass::List ListType;
	typedef typename ListType::const_iterator ListConstIterator;
	typedef typename KeyExtractor::KeyType IndexedFieldType;

	typedef std::multimap<const std::tr1::reference_wrapper<const IndexedFieldType>, ListConstIterator, Comparator> Map;
	typedef typename Map::const_iterator MapConstIterator;

protected:
	enum
	{
		IndexId = BaseIndexerClass::IndexId + 1,
	};

public:

	class const_iterator: public MapConstIterator
	{
	public:
		enum
		{
			IteratorId = IndexId
		};

		const_iterator()
			: MapConstIterator()
		{
		}

		const_iterator(const MapConstIterator& it)
			: MapConstIterator(it)
		{

		}

		const_pointer operator->() const
		{
			return &(**this);
		}

		const_reference operator*() const
		{
			return *getContainerIterator();
		}

		ListConstIterator getContainerIterator() const
		{
			return (*((MapConstIterator*)this))->second;
		}

		const_iterator& operator++()
		{	// preincrement
			++*((MapConstIterator*)this);
			return *this;
		}

		const_iterator operator++(int)
		{	// postincrement
			const_iterator tmp = *this;
			++*this;
			return tmp;
		}

		const_iterator& operator--()
		{	// predecrement
			--*((MapConstIterator*)this);
			return *this;
		}

		const_iterator operator--(int)
		{	// postdecrement
			const_iterator tmp = *this;
			--*this;
			return tmp;
		}
	};

	// iterator type helper
	template<int N>
	class nth_iterator : public BaseIndexerClass::nth_iterator<N>
	{

	};

	template<>
	class nth_iterator<IndexId>
	{
	public:
		typedef const_iterator type;
	};

	// itrator by key
	template<typename Tag>
	class tagged_iterator : public BaseIndexerClass::tagged_iterator<Tag>
	{

	};

	template<>
	class tagged_iterator<IndexTag>
	{
	public:
		typedef const_iterator type;
		enum
		{
			iteratorIndexId = IndexId
		};
	};

	// key type helper
	template<int N>
	class nth_key : public BaseIndexerClass::nth_key<N>
	{

	};

	template<>
	class nth_key<IndexId>
	{
	public:
		typedef IndexedFieldType type;
	};

	// key by tag
	template<typename Tag>
	class tagged_key: public BaseIndexerClass::tagged_key<Tag>
	{

	};

	template<>
	class tagged_key<IndexTag>
	{
	public:
		typedef IndexedFieldType type;
		enum
		{
			keyIndexId = IndexId
		};
	};

	//constructors

	NonUniqueIndex()
	{
	}

	NonUniqueIndex(const NonUniqueIndex& other)
		: BaseIndexerClass(other)
	{
		buildIndex();
	}

	NonUniqueIndex& operator=(const NonUniqueIndex& other)
	{
		BaseIndexerClass::operator=(other);

		buildIndex();
	}

	//begin

	// begin by tag
	template<typename Tag> 
	typename tagged_iterator<Tag>::type begin() const
	{
		return tagged_begin<Tag>();
	}

	// begin by index
	template<int N> 
	typename nth_iterator<N>::type begin() const
	{
		return indexed_begin<N>();
	}

	// end
	// end by tag
	template<typename Tag> 
	typename tagged_iterator<Tag>::type end() const
	{
		return tagged_end<Tag>();
	}

	// end by index
	template<int N> 
	typename nth_iterator<N>::type end() const
	{
		return indexed_end<N>();
	}

	//insert
	bool insert(const value_type& val)
	{
		if (BaseIndexerClass::insert(val))
		{
			const value_type& frontRef = m_data.front();
			m_index.insert(make_pair(std::tr1::cref(KeyExtractor()(frontRef)), m_data.begin()));

			return true;
		}

		return false;
	}

	//erase
	template<typename Iterator>
	void erase(const Iterator& pos)
	{
		// copy iterator to list
		const ListConstIterator listIterator = pos.getContainerIterator();

		internal_erase(listIterator);
	}
	
	template<typename Iterator>
	void erase(const Iterator& from, const Iterator& to)
	{
		Iterator iter = from;
		while (iter != to)
		{
			erase(iter++);
		}
	}

	//tagged erase
	template<typename Tag>
	void erase(const typename tagged_key<Tag>::type& key)
	{
		erase<tagged_key<Tag>::keyIndexId>(key);
	}

	//index erase
	template<int N>
	void erase(const typename nth_key<N>::type& key)
	{
		const std::pair<typename nth_iterator<N>::type, typename nth_iterator<N>::type>& range = equal_range<N>(key);

		const typename nth_iterator<N>::type& end = range.second;
		typename nth_iterator<N>::type iter = range.first;

		while(iter != end)
		{
			erase(iter++);
		}
	}

	// count
	template<int N> 
	size_t count(const typename nth_key<N>::type& key) const
	{
		return indexed_count<N>(key);
	}

	template<typename Tag>
	size_t count(const typename tagged_key<Tag>::type& key) const
	{
		return tagged_count<Tag>(key);
	}

	// find
	template<int N> 
	typename nth_iterator<N>::type find(const typename nth_key<N>::type& key) const
	{
		return indexed_find<N>(key);
	}

	template<typename Tag>
	typename tagged_iterator<Tag>::type find(const typename tagged_key<Tag>::type& key) const
	{
		return tagged_find<Tag>(key);
	}

	// equal_range
	template<int N>
	std::pair<typename nth_iterator<N>::type, typename nth_iterator<N>::type> equal_range(const typename nth_key<N>::type& key) const
	{
		return indexed_equal_range<N>(key);
	}

	template<typename Tag>
	std::pair<typename tagged_iterator<Tag>::type, typename tagged_iterator<Tag>::type> equal_range(const typename tagged_key<Tag>::type& key) const
	{
		return tagged_equal_range<Tag>(key);
	}
	
	// upper bound
	template<int N>
	typename nth_iterator<N>::type upper_bound(const typename nth_key<N>::type& key) const
	{
		return indexed_upper_bound<N>(key);
	}

	template<typename Tag>
	typename tagged_iterator<Tag>::type upper_bound(const typename tagged_key<Tag>::type& key) const
	{
		return tagged_upper_bound<Tag>(key);
	}

	void clear()
	{
		m_index.clear();
		BaseIndexerClass::clear();
	}

protected:
	void internal_erase(const ListConstIterator& pos)
	{
		const std::pair<MapConstIterator, MapConstIterator>& beginAndEnd = m_index.equal_range(std::tr1::cref(KeyExtractor()(*pos)));
		MapConstIterator iter = beginAndEnd.first;
		const MapConstIterator& end = beginAndEnd.second;

		while(iter != end)
		{
			if (pos == iter->second)
			{
				m_index.erase(iter);
				break;
			}
			++iter;
		}

		BaseIndexerClass::internal_erase(pos);
	}

	//internal begin
	template<int N> 
	typename nth_iterator<N>::type indexed_begin() const
	{
		return BaseIndexerClass::indexed_begin<N>();
	}

	template<>
	const_iterator indexed_begin<IndexId>() const
	{
		return const_iterator(m_index.begin());
	}

	template<typename Tag> 
	typename tagged_iterator<Tag>::type tagged_begin() const
	{
		return BaseIndexerClass::tagged_begin<Tag>();
	}

	template<>
	const_iterator tagged_begin<IndexTag>() const
	{
		return const_iterator(m_index.begin());
	}

	//internal end
	template<int N> 
	typename nth_iterator<N>::type indexed_end() const
	{
		return BaseIndexerClass::indexed_end<N>();
	}

	template<>
	const_iterator indexed_end<IndexId>() const
	{
		return const_iterator(m_index.end());
	}

	template<typename Tag> 
	typename tagged_iterator<Tag>::type tagged_end() const
	{
		return BaseIndexerClass::tagged_end<Tag>();
	}

	template<>
	const_iterator tagged_end<IndexTag>() const
	{
		return const_iterator(m_index.end());
	}

	//internal count
	template<int N> 
	size_t indexed_count(const typename nth_key<N>::type& key) const
	{
		return BaseIndexerClass::indexed_count<N>(key);
	}

	template<>
	size_t indexed_count<IndexId>(const IndexedFieldType& key) const
	{
		return m_index.count(std::tr1::cref(key));
	}

	template<typename Tag> 
	size_t tagged_count(const typename tagged_key<Tag>::type& key) const
	{
		return BaseIndexerClass::tagged_count<Tag>(key);
	}

	template<>
	size_t tagged_count<IndexTag>(const IndexedFieldType& key) const
	{
		return m_index.count(std::tr1::cref(key));
	}

	//internal find
	template<int N> 
	typename nth_iterator<N>::type indexed_find(const typename nth_key<N>::type& key) const
	{
		return BaseIndexerClass::indexed_find<N>(key);
	}

	template<>
	const_iterator indexed_find<IndexId>(const IndexedFieldType& key) const
	{
		return m_index.find(std::tr1::cref(key));
	}

	template<typename Tag> 
	typename tagged_iterator<Tag>::type tagged_find(const typename tagged_key<Tag>::type& key) const
	{
		return BaseIndexerClass::tagged_find<Tag>(key);
	}

	template<>
	const_iterator tagged_find<IndexTag>(const IndexedFieldType& key) const
	{
		return m_index.find(std::tr1::cref(key));
	}

	// internal equal range
	template<int N>
	std::pair<typename nth_iterator<N>::type, typename nth_iterator<N>::type> indexed_equal_range(const typename nth_key<N>::type& key) const
	{
		return BaseIndexerClass::indexed_equal_range<N>(key);
	}

	template<>
	std::pair<const_iterator, const_iterator> indexed_equal_range<IndexId>(const IndexedFieldType& key) const
	{
		return m_index.equal_range(std::tr1::cref(key));
	}

	template<typename Tag>
	std::pair<typename tagged_iterator<Tag>::type, typename tagged_iterator<Tag>::type> tagged_equal_range(const typename tagged_key<Tag>::type& key) const
	{
		return BaseIndexerClass::tagged_equal_range<Tag>(key);
	}

	template<>
	std::pair<const_iterator, const_iterator> tagged_equal_range<IndexTag>(const IndexedFieldType& key) const
	{
		return m_index.equal_range(std::tr1::cref(key));
	}

	// internal upper bound
	template<int N>
	typename nth_iterator<N>::type indexed_upper_bound(const typename nth_key<N>::type& key) const
	{
		return BaseIndexerClass::indexed_upper_bound<N>(key);
	}

	template<>
	const_iterator indexed_upper_bound<IndexId>(const IndexedFieldType& key) const
	{
		return m_index.upper_bound(std::tr1::cref(key));
	}

	template<typename Tag>
	typename tagged_iterator<Tag>::type tagged_upper_bound(const typename tagged_key<Tag>::type& key) const
	{
		return BaseIndexerClass::tagged_upper_bound<Tag>(key);
	}

	template<>
	const_iterator tagged_upper_bound<IndexTag>(const IndexedFieldType& key) const
	{
		return m_index.upper_bound(std::tr1::cref(key));
	}

private:
	void buildIndex()
	{
		ListConstIterator it = m_data.begin();
		const ListConstIterator& endIt = m_data.end();

		while(it != endIt)
		{
			const value_type& valRef = *it;
			m_index.insert(make_pair(std::tr1::cref(KeyExtractor()(valRef)), it));
			++it;
		}
	}

	Map m_index;
};

}// namespace MultiIndex

#endif
